package leetcode.每日一题;

import org.junit.Test;

/**
 * @author ：zsy
 * @date ：Created 2023/1/8 9:43 PM
 * @description：
 */
public class 将x减到0的最小操作数 {
    @Test
    public void test() {
        System.out.println(new Solution().minOperations(new int[]{1, 1}, 3));
    }

    class Solution {
        int minOperation = Integer.MAX_VALUE;

        public int minOperations(int[] nums, int x) {
            dfs(nums, x, 0, 0, nums.length - 1);
            return minOperation == Integer.MAX_VALUE ? -1 : minOperation;
        }

        private void dfs(int[] nums, int x, int operationCnt, int l, int r) {
            if (x == 0 || l > r) {
                if (x == 0) {
                    minOperation = Math.min(minOperation, operationCnt);
                }
                return;
            }
            if (nums[l] <= x) {
                dfs(nums, x - nums[l], operationCnt + 1, l + 1, r);
            }
            if (nums[r] <= x) {
                dfs(nums, x - nums[r], operationCnt + 1, l, r - 1);
            }
        }
    }
}
